1. Field of the Invention
The present invention relates generally to a flash file system, and, more particularly, to a Flash Translation Layer (FTL) for intermediating between flash memory and an existing file system, and an address translation method using the FTL.
The present invention is the result of the work which was sponsored by MIC/IITA/ETRI SoC Industry Promotion Center, Human Resource Development Project for IT SoC Architect and the Ministry of Knowledge Economy (MKE) and Korea Industrial Technology Foundation (KOTEF) through the Human Resource Training Project for Strategic Technology
2. Description of the Related Art
Recently, with the commercialization of mass NAND flash memory, the NAND flash memory is attracting attention as new storage devices that will replace magnetic disks in the future. NAND flash memory is advantageous in that it has high input and output speeds because it can make random access, unlike typical hard disks, and it is useful for embedded systems and industrial systems because it is robust against outsider impact. Meanwhile, NAND flash memory has physical characteristics different from those of magnetic disks in addition to the above advantages.
First, NAND flash memory includes pages (512 B or 2 KB) and blocks (16 KB or 128 KB). A page is a minimum unit of NAND flash memory, and 32 or 64 pages generally constitute one block. Second, each of the blocks has a limitation on the number of updates, which is called wear. For example, a Single Level Cell (SLC) has a lifespan corresponding to about a hundred thousand updates, whereas a Multi Level Cell (MLC) has a lifespan corresponding to about ten thousand updates. Third, NAND flash memory is subjected to three operations, that is, read, write and erase operations. The read and write operations are performed on a page basis (512 B or 2 KB), whereas the erase operation is performed on a block basis (16 KB or 128 KB). Fourth, since block-based erase speed is the speed of the erasion of many pages of a block, it is considerably slower than read or write speed.
Meanwhile, since an existing hard disk-dedicated file system is designed regardless of the above-described characteristics of NAND flash memory, the intervention of a Flash Translation Layer (FTL), which is middleware, is required for achieving compatibility between the existing file system and NAND flash memory. The functions of the FTL will be described below.
First, in order to perform in-place update used in the existing file system, an erase-before-write operation must be performed. However, in flash memory, an erase operation is performed on a block basis, so that the cost of erasion is very high. Accordingly, NAND flash memory performs out-place update instead of in-place update, and the FTL performs this out-place update. Second, since NAND flash memory has a specific lifespan, the FTL functions to level the wear over all blocks so that the flash memory can be used for a long time. Third, since erase speed is slower than read or write speed, a garbage collection function of collectively erasing the invalid blocks of flash memory is included.
Meanwhile, the FTL generally uses a page-based address translation technique, but has a problem in that the size of its address translation table is large. In order to overcome this problem, the NAND Flash Translation Layer (NFTL) scheme, which is a block-based address translation scheme, is used. In the NFTL scheme, the quotient obtained by dividing the value of a Logical Block Address (LBA) by the number of pages per block is used as a Virtual Block Address (VBA), and the remainder is used as an offset. Meanwhile, when the address translation table is accessed, an entry having the addresses of a primary block and a replacement block is accessed through the value of the VBA. However, since the NFTL scheme is a block-based translation scheme, replacement blocks must be sequentially searched again if the searching of a primary block for an address fails, with the result that there are defects in that the performance of address translation is low and overhead attributable to address translation is large.
Furthermore, another example of the address translation scheme is the Adaptive Flash Translation Layer (AFTL) scheme. The AFTL uses two-level address translation tables, that is, a coarse-grained hash table, which is a block-based address translation table, and a fine-grained hash table, which is a page-based address translation table. However, the AFTL scheme has a problem in that the amount of memory used is large because tags and points are additionally required.
Moreover, the hash table used in the above-described NFTL scheme and the AFTL scheme has a problem in that about 200% overhead occurs in the amount of memory used because flexibility is lacking due to fixed address translation speed and a tag and a next pointer are additionally required for each node.